#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

const int N = 5e4 + 500, M = 4e5+500;

typedef long long LL;

namespace dinic
{
struct E
{
    int to;
    LL cp;
    E(int to = 0, LL cp = 0) : to(to), cp(cp) {}
};
struct Dinic
{
    static const int INF = 0x7fffffff;
    int m, s, t, n;

    E edges[M];
    int ecnt;
    vector<int> G[N];

    int d[N], cur[N];

    void init(int n, int s, int t)
    {
        this->s = s;
        this->t = t;
        this->n = n;
        ecnt = m = 0;
        for (int i = 0; i <= n; ++i)
            G[i].clear();
    }

    void addedge(int u, int v, LL cap)
    {
        edges[ecnt++] = E(v, cap);
        edges[ecnt++] = E(u, 0);
        G[u].push_back(m++);
        G[v].push_back(m++);
    }

    bool bfs()
    {
        memset(d, 0, sizeof(int) * (n + 2));
        queue<int> Q;
        Q.push(s);
        d[s] = 1;
        while (!Q.empty())
        {
            int x = Q.front();
            Q.pop();
            for (int &i : G[x])
            {
                E &e = edges[i];
                if (!d[e.to] && e.cp > 0)
                {
                    d[e.to] = d[x] + 1;
                    Q.push(e.to);
                }
            }
        }
        return d[t];
    }

    LL DFS(int u, LL cp)
    {
        if (u == t || !cp)
            return cp;
        LL tmp = cp;
        LL f;
        for (int &i = cur[u]; i < (int)G[u].size(); ++i)
        {
            E &e = edges[G[u][i]];
            if (d[u] + 1 == d[e.to])
            {
                f = DFS(e.to, min(cp, e.cp));
                e.cp -= f;
                edges[G[u][i] ^ 1].cp += f;
                cp -= f;
                if (!cp)
                    break;
            }
        }
        return tmp - cp;
    }

    LL go(int S = -1, int T = -1)
    {
        if ((~S) && (~T))
        {
            s = S;
            t = T;
        }
        LL flow = 0;
        while (bfs())
        {
            memset(cur, 0, sizeof(int) * (n + 1));
            flow += DFS(s, INF);
        }
        return flow;
    }

    void dbg()
    {
        for (int i = 1; i <= n; ++i)
        {
            printf("i=%d, ", i);
            for (int j : G[i])
                printf("{id: %d, to:%d, cp:%lld} ", j, edges[j].to, edges[j].cp);

            puts("");
        }
    }
};
} // namespace dinic

class extdinic1
{
public:
    dinic::Dinic dc;
    int S, T;
    LL tf[N];
    LL sum;

    void init(int n, int m, int u[], int v[], int w1[], int w2[])
    {
        S = ++n;
        T = ++n;
        dc.init(n, S, T);
        memset(tf, 0, sizeof(LL) * (n + 1));
        for (int i = 0; i < m; ++i)
        {
            tf[v[i]] += w1[i];
            tf[u[i]] -= w1[i];
            dc.addedge(u[i], v[i], w2[i] - w1[i]);
        }
        sum = 0;
        for (int i = 1; i <= n - 2; ++i)
        {
            if (tf[i] < 0)
            {
                dc.addedge(i, T, -tf[i]);
            }
            else if (tf[i] > 0)
            {
                dc.addedge(S, i, tf[i]);
                sum += tf[i];
            }
        }
    }

    LL go()
    {
        LL ans = dc.go();
        if (ans != sum)
            return -1;
        else
            return ans;
    }

    void printTrace(int m, int w1[])
    {
        for (int i = 0; i < m; ++i)
        {
            int reveid = i << 1 | 1;
            printf("%lld\n", dc.edges[reveid].cp + w1[i]);
        }
    }
};

class extdinic2 : public extdinic1
{
public:
    static const LL INF = 1e18;
    int s, t;

    void init(int n, int m, int s, int t, int u[], int v[], int w1[], int w2[])
    {
        this->s = s;
        this->t = t;
        extdinic1::init(n, m, u, v, w1, w2);
    }
    LL go()
    {
        dc.addedge(t, s, INF);
        LL ans = extdinic1::go();
        if (ans == -1)
            return -1;
        ans = dc.go(s, t);
        return ans;
    }

    void trace(int eids[], int ecnt, int w1[], LL res[])
    {
        for (int i = 0; i < ecnt; ++i)
        {
            int x = eids[i] << 1 | 1;
            res[i] = dc.edges[x].cp + w1[eids[i]];
        }
    }
};

class extdinic3 : public extdinic2
{
public:
    LL go()
    {
        dc.addedge(t, s, INF);
        LL ans = extdinic1::go();
        if (ans == -1) return -1;
        ans = dc.edges[dc.ecnt-1].cp;
        dc.edges[dc.ecnt-1].cp = dc.edges[dc.ecnt-2].cp = 0;
        ans -= dc.go(t, s);
        return ans;
    }   
} dc;

int u[M], v[M], w1[M], w2[M];